import numpy as np


def crf_viterbi(tk, sl, l, n):
    #条件随机场的viterbi算法
    '''
    :param tk:定义在边上的特征函数，ndarray,
    :param sl: 定义在节点上的特征函数，ndarray,
    :param l: 随机变量可以取的值，ndarray,
    :param n: 观测序列的长度,int,也就是位置的个数
    :return: 最优的标记序列，由l里面的值组成的数组,ndarray
    '''

    #第一步：初始化：
    #定义最优标记序列
    best_tag_list = []
    tag_num = l.shape[0]
    delta = np.zeros([n, tag_num])
    for i in range(tag_num):
        delta[0][i] = sl[0][i]
    best_tag_list.append(np.argmax(delta[0]))

    #第二步递推：
    for i in range(1, n): #遍历位置，当前位置i，上一位置i-1
        for l in range(tag_num): #遍历可选的标签
            #计算的是delta[i][l],因为取最大非规范化概率，需要遍历
            max = 0
            for j in range(tag_num):
                #使用tk中的第 i - 1个矩阵概率
                #使用sl中的当前第 i 个结点的概率
                p = delta[i-1][j] + tk[i-1][j][l] + sl[i][l];
                if p > max:
                    max = p
            delta[i][l] = max
        best_tag_list.append(np.argmax(delta[i]))
    return best_tag_list

if __name__ == "__main__" :
    sl = np.array([[1, 0.5],
          [0.8, 0.5],
          [0.8, 0.5]])
    tk = np.array([[[0.6, 1], [1, 0]], [[0, 1], [1, 0.2]]])
    l = np.array([1,2])
    n = 3

    crf_viterbi(tk, sl, l, n)
